package LC;

import java.util.Arrays;

/**
 * @ClassName LC41
 * @Description: TODO
 * @Author hl
 * @Date 2021/4/24
 * @Version V1.0
 **/
public class LC41 {
    public static int firstMissingPositive(int[] nums) {
        int n=nums.length;
        for(int i=0;i<n;i++){
            if(nums[i]<=0){
                nums[i]=n+1;
            }
        }
        for(int i=0;i<n;i++){
            int target=Math.abs(nums[i]);
            if(target>=1&&target<=n){
                nums[target-1]=-Math.abs(nums[target-1]);
            }
        }
        for(int j=0;j<nums.length;j++){
            if(nums[j]>0){
                return j+1;
            }
        }
        return n+1;
    }

    public static void main(String[] args) {
        int []nums={3,4,-1,1};
        System.out.println(firstMissingPositive(nums));
    }
}
